package LIst;

public class MySingLeList {
    static class ListNode{
        public  int value;
        public  ListNode next;

        public ListNode(int value) {
            this.value = value;
        }
    }

    public ListNode head;
    public ListNode head2;

    public  void creatList1(){
        ListNode listNode1 =new ListNode(1);
        ListNode listNode2 =new ListNode(2);
        ListNode listNode3 =new ListNode(3);
        ListNode listNode4 =new ListNode(4);
        ListNode listNode5 =new ListNode(5);

        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode4;
        listNode4.next=listNode5;

        this.head=listNode1;
    }
    public  void creatList2(){
        ListNode listNode1 =new ListNode(6);
        ListNode listNode2 =new ListNode(7);
        ListNode listNode3 =new ListNode(3);
        ListNode listNode4 =new ListNode(4);
        ListNode listNode5 =new ListNode(5);

        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode4;
        listNode4.next=listNode5;

        this.head2=listNode1;
    }
    public  void display(){
        ListNode cur =head;
        while (cur!=null){
            System.out.print(cur.value+" ");
            cur=cur.next;
        }
        System.out.println("");
    }
    public  void display(ListNode newhead){ //重载可以从当前位置结点打印而不是一味的头节点
        ListNode cur =head;
        while (cur!=null){
            System.out.print(cur.value+" ");
            cur=cur.next;
        }
        System.out.println("");
    }
    public  void addFirst(int data){
        ListNode node=new ListNode(data);
        node.next=head;
        head=node;
    }
    public  void addLast(int data){
        ListNode node= new ListNode(data);
        if(head==null){
            head=node;
        }
        else {
            ListNode cur=head;
            while (cur.next!=null){
                cur=cur.next;
            }
            cur.next=node;
        }
    }
    private  boolean cheak(int index){
        if(index<0||index>size()){
            throw new MycheakException("插入不合法");
        }
        return  true;
    }
    public  void addIndex(int index,int data){
        cheak(index);
        if (index==0){
            addFirst(data);
            return;
        }
        if(index==size()){
            addLast(data);
            return;
        }
        ListNode cur =find(index);
        ListNode node = new ListNode(data);
        node.next=cur.next;
        cur.next=node;
    }
    public ListNode find(int index){
        ListNode cur =this.head;
        while (index-1!=0){
            cur = cur.next;
            index--;
        }
        return cur;
    }
    public  void remove(int key){
        ListNode cur=head;
        if(head==null){
            System.out.println("errror");
            return;
        }
        if(head.value==key){
            head=null;
            return;
        }
        while (cur.next!=null){
            if (cur.next.value==key){
                ListNode del=cur.next;
                cur.next=del.next;
                return;
            }
            cur=cur.next;
        }
    }
    public  void removeAllkey(int key){
        if(head==null){
            System.out.println("errror");
            return;
        }
        ListNode cur =this.head.next;
        ListNode prev =this.head;
        while (cur!=null){
            if(cur.value==key){
                prev.next=cur.next;
                cur=cur.next;
            }
            else {
                prev=cur;
                cur=cur.next;
            }
            if(head.value==key){
                head=head.next;
            }
        }
        /*ListNode cur=head;
        while (cur.next!=null){
            while (cur.next.value==key||cur.value==key){
                ListNode del=cur.next;
                cur.next=del.next;
            }
            cur=cur.next;
        }*/
    }
    public  int size(){
        ListNode cur =head;
        int count=0;
        while (cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }
    public  void clear(){
        //head=null;粗暴做法
        ListNode curNext = null;
        ListNode cur =head;
        while (cur!=null){
            cur.next=null;
            curNext=cur.next;
            cur=curNext;
        }
        head=null;
    }
    public  boolean cantions(int key){
        ListNode cur =head;
        while (cur!=null){
            if(cur.value==key){
                return true;
            }
            cur=cur.next;
        }
        return  false;
    }

    public ListNode reserve(){//逆序
        if(head==null){
            return null;
        }
        if(head.next==null){
            return  head;
        }
        ListNode cur =head.next;
        head.next=null;

        while (cur!=null){
            ListNode curNext =cur.next;
            cur.next=head;
            head=cur;
            cur=curNext;
        }
        return head;
    }

    public ListNode middle(){ //找中间的结点
        ListNode fast=head;
        ListNode slow =head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        //head=slow;
        return slow;
    }

    public ListNode findlastindex(int k){//找到倒数第几个节点
        //1:倒数k就是正数size-k步；
        //2：遍历一边 可以用fastandslow； //求倒数第k步就fast先走k-1步，然后一起走fast走到头最后slow的地方就是倒数第k步

        cheak(k);
        if(head==null){
            return null;
        }
        ListNode slow=head;
        ListNode fast=head;
        while (k-1!=0){  //k-1步
            fast=fast.next;
            k--;
        }
        while (fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }

    public ListNode hebing(ListNode head1,ListNode head2){//两个链表由小到大链接
        if(head1==null){
            return head2;
        }
        if(head2==null){
            return head1;
        }
        ListNode newhead =new ListNode(-1); //傀儡头节点，不用它的值，只用它的next；
        ListNode tmp= newhead;
        while (head1 != null && head2 != null){
            if(head1.value<head2.value){
                tmp.next=head1;
                tmp=head1;
                head1=head1.next;
            }else {
                tmp.next=head2;
                tmp=head2;
                head2=head2.next;
            }
        }
        if(head1!=null){
            tmp.next=head1;
        }
        else if (head2!=null){
            tmp.next=head2;
        }
        return newhead.next;
    }

    // 回文意思: 1-》2-》2—》1
    public boolean huiweng (){
        if(head.next==null){
            return  false;
        }
        if (head.next==null){
            return false;
        }
        ListNode fast =head;
        ListNode slow =head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        ListNode cur =slow.next;
        ListNode curnext=cur.next;
        while (cur!=null){
            curnext=cur.next;
            cur.next=slow;
            slow=cur;
            cur=curnext;
        }
        while (head!=slow){
            if(head.value!=slow.value){
                return false;
            }
            if(head.next==slow){ //偶数情况下，先判断值一样然后就不走了
                return  true;
            }
            head=head.next;
            slow=slow.next;
        }
        return true;
    }
    public  ListNode paixulimition(int x){
        ListNode bs =null;
        ListNode be =null;
        ListNode as =null;
        ListNode ae =null;

        ListNode cur =head;
        while (cur!=null){
            if(cur.value<=x){
                if(bs==null){
                    bs=cur;
                    be=cur;
                }
                else {
                    be.next=cur;
                    be=be.next;
                }
            }
            else {
                if(as==null){
                    as=cur;
                    ae=cur;
                }
                else {
                    ae.next=cur;
                    ae=ae.next;
                }
            }
            cur= cur.next;
        }
        if(bs==null){
            return as;
        }
        be.next=as;

        if(as!=null){
            ae.next=null;
        }
        return  bs;
    }

    public  ListNode equals(ListNode head, ListNode head2){ //找两链表相交的结点 前提是有一个相交的链表
        if(head==null||head2==null){
            return null;
        }
        int len1=0;
        int len2=0;
        ListNode p1 =head;
        ListNode p2 =head2;
        while (p1!=null){
            len1++;
            p1=p1.next;

        }
        while (p2!=null){
            len2++;
            p2=p2.next;

        }
        p1=head;
        p2=head2;
        int len = len1-len2;
        if(len<0){  //p1 一定指向最长的链表 len是差值 先走的步数后一起走才可以计算
            p1=head2;
            p2=head;
            len =len2-len1;
        }
        while (len!=0){
            p1=p1.next;
            len--;
        }
        while (p1!=p2){
            p1=p1.next;
            p2 =p2.next;
        }
        return p1;
    }

    public  ListNode cycle(){ //判断环，并且返回入环的第一个结点的的结点
        if(head==null){
            return null;
        }
        ListNode fast=head;
        ListNode slow =head;
        while (fast!=null&&fast.next!=null){
            fast =fast.next.next;
            slow =slow.next;
            if(fast==slow){
                break;
            }
        }
        slow=head;//相遇后不一定是环的第一个结点，此时让slow重新开始，下一次相遇就一定是第一次相遇的结点
        while (slow!=fast){
            slow=slow.next;
            fast=fast.next;
        }
        return  slow;
    }
    public ListNode deleteDuplication(ListNode pHead) {//删除链表中重复的结点
            if(pHead==null){
                return null;
            }
            ListNode newHead=new ListNode(-1);
            newHead.next=pHead;
            ListNode cur=newHead;
            ListNode slow=pHead;
            ListNode fast=pHead.next;
            while(fast!=null){
                if(slow.value!=fast.value){
                    cur=slow;
                    slow=fast;
                    fast=fast.next;
                }else{
                    while(fast!=null&&slow.value==fast.value){
                        fast=fast.next;
                    }
                    cur.next=fast;
                    if(cur.next!=null){
                        slow=fast;
                        fast=fast.next;
                    }
                }
            }
            return newHead.next;
        }
}
